package com.cqs.leetcode.dp;

import java.util.Arrays;

/**
 * lixw
 * 2021/11/17
 **/
public class MaximumWordLengths318 {
    private class Node {
        // 1011...1//26個長度
        char[] chars = new char[26];
        int strLen = 0;
    }

    public int maxProduct(String[] words) {
        Node[] nodes = new Node[words.length];
        int idx = 0;
        for (String word : words) {
            Node node = new Node();
            node.strLen = word.length();
            for (int i = 0; i < word.length(); i++) {
                node.chars[word.charAt(i) - 'a'] = 1;
            }
            nodes[idx++] = node;
        }

        //倒排
        Arrays.sort(nodes, (o1, o2) -> o2.strLen - o1.strLen);
        int max = 0;
        for (int i = 1; i < nodes.length; i++) {
            //减支
            if (nodes[i].strLen * nodes[0].strLen <= max) {
                break;
            }
            for (int j = 0; j < i; j++) {
                //减支
                if (nodes[i].strLen * nodes[j].strLen <= max) {
                    break;
                }
                if (!hasSameCharacter(nodes[i], nodes[j])) {
                    max = Math.max(max, nodes[i].strLen * nodes[j].strLen);
                }
            }
        }
        return max;
    }

    private boolean hasSameCharacter(Node n, Node n2) {
        for (int i = 0; i < 26; i++) {
            if (n.chars[i] == 1 && n.chars[i] == n2.chars[i]) return true;
        }
        return false;
    }
}
